\section{Ejercicio 1}
\subsection{Introducci\'on}
\setlength{\parindent}{2em}
En el presente ejercicio, dado un grafo $G$ con pesos asociados a sus aristas, los cuales forman un circuito simple. Se pretende obtener el peso del matching m'aximo.\\
Un matching es un conjunto de ejes de $G$ que no comparten v'ertices. El peso del matching va a ser la suma de los pesos de sus ejes, en nuestro caso nos va a interesar alg'un matching de m'aximo peso. En este problema la cantidad de nodos de $G$ ser'a $\geq$ 3.
Para dejar mas clara la idea, veamos un peque'no ejemplo:

\begin{itemize}
 \item Grafo con 6 vertices y 6 aristas con pesos propios.
 \item El grafo es constituido por un 'unico circuito simple.
\end{itemize}

\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{./dibujitos/Grafo1.png}
	\caption{Grafo conexo y con un 'unico ciruito, rotulado con pesos en la aristas} 
\end{figure}


Debemos chequear que conjunto de aristas consigue el peso m'aximo, verificando que se cumpla la condici'on de matching: \\

\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{./dibujitos/Grafo2.png}
	\caption{Los ejes marcados que verifican ser el matching m'aximo} 
\end{figure}

Con lo cual el matching m'aximo aqu'i es el que consigue un peso de: a{1} = 6 + a{2} = 7 + a{3} = 2, o sea, 15.\\
A simple vista a uno podria ocurrirsele que usar un algoritmo goloso podr'ia funcionar de forma correcta, lo cual es facilmente refutable con m'as de un contraejemplo. Debido a esto tuvimos que idear otra estrateg'ia no tan intuitiva en un primer momento, pero que usa otra de la t'ecnicas conocidas en el dise\~no de algoritmos eficientes, la programaci'on din'amica.\\ 
Dado que 'esta es s'olo una mera introducci\'on, todas estas dificultades y detalles de la resoluci'on del problema las detallaremos en la pr'oxima secci'on.

\newpage

\subsection{Soluci\'on}
La idea que surge pensando el problema es utilzar la t'ecnica de programaci'on din'amica para resolverlo de forma eficiente. Esta t'ecnica nos va a permitir constatar todas las posibilidades, almacenando cierta informaci'on de forma tal que al calcular el matching lo haga de forma eficiente y no se repitan c'alculos. Construyendo la soluci'on 'optima paso a paso valiendonos del principio de optimalidad inherente a este problema. Logrando as'i reducir significativamente la complejidad del algoritmo, aunque la dificultad reside en donde y como almacenar la informaci'on de modo de que sea de utilidad para reutilizar c'alculos previamente realizados.\\
Pero para conseguir esto, como primer medida tenemos que encontrar una funci'on recursiva que consiga la soluci\'on 'optima, y ver que se cumpla el principio de optimaliadad.\\ 
Para poder expresar la funci'on recursiva debemos considerar que caracter'istica tiene que cumplir nuestra soluci'on, m'as concretamente que aristas van a estar en el conjunto soluci'on.\\
Como en todos los problemas en que se usa la t'ecnica de programaci'on din'amica, asumimos que sabemos cual es la soluci'on 'optima, llamemosla $S$. Entonces deber'iamos determinar que caracter'istica tendr'ia que cumplir un eje del grafo $G$. Investigando detenidamente con varios grafos, llegamos a la conclusi'on de que cada eje $e$ tiene dos opciones: $e$ $\in$ $S$ 'o $e$ $\notin$ $S$.\\
En caso de que $e$ $\in$ $S$, por la definici'on de matching sabemos que los ejes que compartan v'ertices con $e$ en $G$ no deben pertenecer a la soluci'on. En el otro caso no habr'a restricciones sobre los dem'as v'ertices. \\
Adem'as sabemos que para que un matching sea el de m'aximo peso, 'este debe ser maximal ya que los pesos de los ejes son positivos. Con lo cual no podr'ia existir ning'un eje de $G$ que no comparta v'ertices con los ejes de $S$ y no pertenezca al matching m'aximo.\\
Esto nos da la idea de la funci'on recursiva que buscamos ya que nuestro objetivo es conseguir el m'aximo entre un matching en el cual est'e el eje $e$ y uno en el que no est'e el eje $e$. La cual explicaremos detalladamente en la pr'oxima secci'on.\\
La decisi'on de elegir programaci'on d'inamica y no otra t'ecnica algoritmica conocida radica en que notamos, luego de haber encontrado la funci'on recursiva que resolv'ia el problema, subproblemas superpuestos. Estos subproblemas superpuestos se deben a que los subproblemas no son completamente independientes entre s'i, con lo cual usar otra t'ecnica que no evitar'a la repetici'on de c'alculos producida por esta dependencia podria conllevar a una soluci'on poco eficiente.\\   
Una vez que conseguimos nuestra funci'on, debemos constatar que se verifica el principio de optimalidad. En caso contrario no ser'a posible aplicar programaci'on d'inamica como metodolog'ia para la resoluci\'on del problema. Detalle en la explicaci'on (secci'on 1.3).\\ 
Una vez encontrada la funci'on y verificado que vale el principio de optimalidad, nos encontramos con la dificultad de la implementaci'on. La primer opci'on fue sobre una matriz $\in$ $\mathbb{R}^{n x n}$ con n cantidad de ejes de $G$. Con lo cual obtenemos una complejidad de orden cuadr'atico con respecto a los ejes, ya que la idea era llenar los casilleros de la matriz con las posibles combinaciones hasta llegar a la que buscamos.\\
Luego decidimos implementar el algoritmo sobre un arreglo de tama\~no {\bf n} y as'i poder lograr la complejidad deseada, de orden lineal.\\
Finalmente notamos que el arreglo 'unicamente depend'ia de 2 valores anteriores, ya que solamente era necesario conocer 2 posiciones antecesoras para construir el valor de la posici'on actual. Con lo cual reducimos la complejidad espacial al uso de 3 variables auxiliares aunque la complejidad temporal no cambia debido a que se recorre una 'unica vez cada eje. Logrando as'i un recorrido lineal de todas las aristas del grafo. \\
En las pr'oximas secciones detalleremos el funcionamiento del algoritmo.

\newpage

\subsection{Funci'on recursiva}
 
Sea \textbf{K} una lista de entrada del algoritmo y \textbf{$a_1$,$a_2$,...,$a_n$} sus elementos numerados. \\ matchingMaximo($a_1$,$a_2$,...,$a_n$) = max(matchingMaximoAux($a_1$,$a_2$,...,$a_{n-1}$)), matchingMaximoAux($a_2$,...,$a_{n-2}$)+$a_n$)
\newline
\newline
Casos posibles al llamar al algoritmo matchingMaximoAux:
\begin{itemize}
	\item matchingMaximoAux($\emptyset$) = $0$ 
	\item matchingMaximoAux($a_1$) = $a_1$ 
	\item matchingMaximoAux($a_1$,$a_2$) = max($a_1$, $a_2$) 
	\item matchingMaximoAux($a_1$,$a_2$,$a_3$) = max($a_2$, $a_1$ + $a_3$) 
	\item matchingMaximoAux($a_1$,$a_2$,...,$a_n$) (con \textbf{n} $>$ 3) =\\ max(matchingMaximoAux($a_1$,$a_2$,...,$a_{n-1}$)), matchingMaximoAux($a_1$,$a_2$,...,$a_{n-2}$) + $a_n$)
\end{itemize}

\subsubsection{Explicaci'on}

La funci'on matchingMaximo s'olo llama a matchingMaximoAux, pero no se llama recursivamente. \textbf{K} representa un ciclo de aristas cuando
ingresa como par'ametro de matchingMaximo, pero cuando ingresa a matchingMaximoAux es el mismo conjunto de aristas sin una, con lo cual ya no se forma un ciclo.

matchingMaximoAux($a_1$,$a_2$,...,$a_n$) / \textbf{n} $>$ 3 = max(\textbf{A},\textbf{B})\\

\begin{itemize}
 	\item \textbf{A}: devuelve el matching m'aximo sin tomar en cuenta la arista $a_n$.
 	\item \textbf{B}: devuelve el matching m'aximo sin tomar en cuenta la arista $a_{n-1}$ pero considerando a $a_n$ como parte del matching m'aximo.
\end{itemize}

Inicialmente \textbf{K} tiene la forma:

\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{./dibujitos/grafocircular3.png}
\end{figure}

Al llamar a matchingMaximoAux puede tener la siguiente forma:

\begin{figure}[H]
	\centering	
		\includegraphics[width=0.4\textwidth]{./dibujitos/grafocircular4.png}
\end{figure}
\newpage

O podr'ia tener esta forma:

\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{./dibujitos/grafocircular5.png}
\end{figure}
 
En ambos casos nos queda un grafo sin ciclos, un camino.

\subsubsection{Principio de optimalidad}
Vamos a verificar la validez del principio: \\
\\
Tenemos un matching m'aximo para un grafo de n aristas $\Rightarrow$ cada subgrafo con k($<$ n) aristas tambi'en es \newline matching m'aximo. 
Para esto 'ultimo debemos recalcar que el subgrafo que cumpla ser matching m'aximo deber'a ser maximal, de lo contrario, podr'iamos extenderlo con alguna arista que no comparta v'ertices con las ya existentes en el subgrafo y mejorar el matching que teniamos como soluci'on. Esto se debe a que el peso de las aristas son positivos, en otro caso no ser'ia tan trivial la decisi'on y verificaci'on de optimalidad.  

\begin{flushleft}
\subsubsection{\textquestiondown{Por qu'e la soluci'on es 'optima?}}

Queremos ver que para cualquier grafo de entrada con n($>$ 3) aristas y ciclico, el algoritmo devuelve el matching de m'aximo peso.\\
Entonces desarrollemos la funci'on con esta cantidad de elementos y verifiquemos que la soluci'on es 'optima.\\
\medskip
Sabemos que matchingMaximo lo 'unico que hace es tomar el m'aximo valor entre los dos llamados a matchingMaximoAux. Ahora bien, si matchingMaximoAux devuelve el matching de m'aximo peso con las aristas pasadas como par'ametro, entonces la soluci'on va a ser 'optima.\\
Lo que debemos chequear para matchingM'aximo es que a la funci'on matchingMaximoAux no le pasamos un grafo ciclico, sino que le pasamos un camino simple.
Veamos como queda el grafo:\\
\medskip
\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{./dibujitos/grafocircular3.png}
	\caption{Grafo ciclico de n aristas}
\end{figure}
matchingMaximo($a_1$,$a_2$,...,$a_{n-1}$,$a_{n}$) = \\
max(matchingMaximoAux($a_1$, $a_2$,..., $a_{n-1}$)), matchingMaximoAux($a_2$,..., $a_{n-2}$) + $a_{n}$) = max(\textbf{A},\textbf{B}).
\newpage
\begin{itemize}
	\item \textbf{A}: llama a matchingMaximoAux sin considerar a $a_{n}$.
		\begin{figure}[H]
			\centering
				\includegraphics[width=0.4\textwidth]{./dibujitos/grafocircular4.png}
		\end{figure}
	\item \textbf{B}: llama a matchingMaximoAux considera a $a_{n}$, y como est'a unido a  $a_{n-1}$ y $a_1$ no los tiene en cuenta.
		\begin{figure}[H]
			\centering
				\includegraphics[width=0.4\textwidth]{./dibujitos/grafocircular8.png}
		\end{figure}
	\end{itemize}

Lo que nos falta es probar que la funci'on matchingMaximoAux devuelve la soluci'on 'optima. Es la que realiza la recursi'on sobre la lista de entrada que representa el subgrafo sin ciclos(es un camino simple) resultante de quitarle las aristas correspondientes a cada caso. \\
La funci'on matchingMaximo solamente toma el m'aximo valor resultante de las dos llamadas a matchingMaximoAux con el grafo sin ciclos resultante de tomar o no a $a_{n}$ como parte del matching m'aximo.\\ 
Con lo cual si demostramos que matchingMaximoAux($y_1$...$y_{n}$) es el matching m'aximo para esos elementos se lograr'ia demostrar matchingMaximo.\\
Entonces demostremos esto 'ultimo usando {\bf inducci'on} en n, con n = cantidad de aristas del subgrafo. 

\medskip
\fbox{{\bf Casos base:}} 
\begin{itemize}
 

	\item n = 0 : matchingMaximoAux($\emptyset$) = $0$ \\
	Es cierto que para n = 0 es 'optimo ya que el matching m'aximo es 0.
	\item n = 1 : matchingMaximoAux($a_1$) = $a_1$ \\
	Es cierto que para n = 1 es 'optimo ya que el matching m'aximo es tomar solo $a_1$ 
	\item n = 2 : matchingMaximoAux($a_1$,$a_2$) = max($a_1$, $a_2$) \\
	Es cierto que para n = 2 es 'optimo ya que el matching m'aximo es tomar el m'aximo entre $a_1$ o tomar $a_2$.
	\item n = 3 : matchingMaximoAux($a_1$,$a_2$,$a_3$) = max($a_2$, $a_1$ + $a_3$)\\
	Es cierto que para n = 3 es 'optimo ya que el matching m'aximo es tomar solo $a_2$ o tomar $a_1$ y $a_3$, estas 'ultimas no est'an conectados entre s'i. 
\end{itemize}

\newpage
 
\fbox{{\bf Paso inductivo:}}\\
\medskip
Sea {\bf HI}: Para un grafo de k aristas, con k $\leq$ n, la funci'on matchingMaximo($a_1$, ..., $a_k$) devuelve el matching de peso m'aximo.\\ 

Queremos ver que P(n) $\Rightarrow$ P(n+1), con n $>$ 3 y grafo de entrada sin ciclos.\\
Apliquemos la definici'on de la funci'on, recordar que el grafo en este punto forma un camino:\\
\medskip
matchingMaximoAux($a_1$, $a_2$,..., $a_{n+1}$) = \\
max(matchingMaximoAux($a_1$, $a_2$,..., $a_{n}$)), matchingMaximoAux($a_1$, $a_2$,...,$a_{n-1}$) + $a_{n+1}$)\\
\medskip
Como matchingMaximoAux($a_1$,$a_2$,...,$a_{n}$) = \\
max(matchingMaximoAux($a_1$, $a_2$,..., $a_{n-1}$)), matchingMaximoAux($a_1$, $a_2$,..., $a_{n-2}$) + $a_{n}$)\\ 
\medskip
Entonces cosiderando lo anterior podemos reescribir matchingMaximoAux para n + 1 elementos de la siguiente forma: \\
\medskip
matchingMaximoAux($a_1$, $a_2$,..., $a_{n+1}$) = \\
max( max(matchingMaximoAux($a_1$,$a_2$,...,$a_{n-1}$)), matchingMaximoAux($a_1$,$a_2$,...,$a_{n-2}$) + $a_{n}$, 
matchingMaximoAux($a_1$,$a_2$,...,$a_{n-1}$) + $a_{n+1}$)\\
\medskip
Y esto 'ultimo se puede reescribir de la siguiente manera:\\
\medskip
matchingMaximoAux($a_1$,$a_2$,...,$a_{n+1}$) = \\
max(matchingMaximoAux($a_1$,$a_2$,...,$a_{n-2}$) + $a_{n}$, matchingMaximoAux($a_1$,$a_2$,...,$a_{n-1}$)+$a_{n+1}$)\\
\medskip
Entonces es cierto que es 'optima porque tanto matchingMaximoAux($a_1$,$a_2$,...,$a_{n-2}$) como matchingMaximoAux($a_1$,$a_2$,...,$a_{n-1}$) son 'optimas por {\bf HI}, porque es usar $a_{n}$ o $a_{n+1}$ para el matching m'aximo y llamar recursivamente a matchingMaximoAux con una lista con un elemento menos(n elementos).\\
Con lo cual podemos concluir que la soluci'on que devuelve el algoritmo es la 'optima. 
\end{flushleft}

\newpage

\subsection{Pseudoc'odigos}
	\subsubsection{Versi'on recursiva}
	\newcommand{\matchingMaximoRec}{\ensuremath{\mbox{\sc matchingMaximoRec}}}
	\begin{algorithm}[H]
		\caption{$\matchingMaximoRec(pesos:[Nat], long: int)$}\label{alg:matchingMaximoRec}
			\medskip
			\begin{algorithmic}[1]
			\STATE devolver\\ 
				max( matchingMaximoRecAux(pesos$_{0...long-2}$, long - 1), \\
			        matchingMaximoRecAux(pesos$_{1...long-3}$, long - 3) + pesos$_{long-1}$ ) 
			\end{algorithmic}
	\end{algorithm}
	
	\newcommand{\matchingMaximoRecAux}{\ensuremath{\mbox{\sc matchingMaximoRecAux}}}
	\begin{algorithm}[H]
		\caption{$\matchingMaximoRecAux(pesosSubList:[Nat], subLong: int)$}\label{alg:matchingMaximoRecAux}
			\medskip
			\begin{algorithmic}[1]
			\IF{(subLong == 0)}
				\STATE devolver 0
			\ENDIF
			\IF{(subLong == 1)}
				\STATE devolver pesosSubList$_{0}$
			\ENDIF
			\IF{(subLong == 2)}
				\STATE devolver max(pesosSubList$_{0}$, pesosSubList$_{1}$)
			\ENDIF
			\IF{(long == 3)}
				\STATE devolver max(pesosSubList$_{1}$, pesosSubList$_{0}$ + pesosSubList$_{2}$)
			\ELSE
				\STATE devolver 
 				\STATE max(matchingMaximoRecAux(pesosSubList$_{0...long - 2}$,subLong - 1),
 				\STATE matchingMaximoRecAux(pesosSubList$_{0...long - 3}$,subLong - 2) + pesosSubList$_{long - 1}$))
			\ENDIF
			\end{algorithmic}
	\end{algorithm}

	\newpage

	\subsubsection{Versi'on iterativa}
	
	\newcommand{\matchingMaximoIter}{\ensuremath{\mbox{\sc matchingMaximoIter}}}
	\begin{algorithm}[H]
		\caption{$\matchingMaximoIter(pesos:[Nat], long: int)$}\label{alg:matchingMaximoIter}
			\medskip
			\begin{algorithmic}[1]
			\STATE devolver max(matchingMaximoAux(pesos$_{0...long - 2}$, long - 1),\\ 
			\STATE matchingMaximoIterAux(pesos$_{1...long - 3}$, long-3) + pesos$_{long - 1}$)
		\end{algorithmic}
	\end{algorithm}
	
	
	\newcommand{\matchingMaximoIterAux}{\ensuremath{\mbox{\sc matchingMaximoIterAux}}}
	\begin{algorithm}[H]
		\caption{$\matchingMaximoIterAux(pesosSubList:[Nat], subLong: int)$}\label{alg:matchingMaximoIterAux}
			\medskip
			\begin{algorithmic}[1]
			\STATE Integer resA, resB, resC
			\IF{(subLong == 0)}
				\STATE devolver 0
			\ENDIF
			\IF{(subLong == 1)}
				\STATE devolver pesosSubList$_{0}$
			\ENDIF
			\IF{(subLong == 2)}
				\STATE devolver max(pesosSubList$_{0}$, pesosSubList$_{1}$)
			\ENDIF
			\IF{(subLong == 3)}
				\STATE devolver max($pesosSubList_{1}$, $pesosSubList_{0}$ + $pesosSubList_{2}$)
			\ELSE
					\STATE resA $\leftarrow$ pesosSubList$_{0}$
					\STATE resB $\leftarrow$ max(pesosSubList$_{0}$, pesosSubList$_{1}$)
					\STATE resC $\leftarrow$ max(pesosSubList$_{1}$, pesosSubList$_{0}$ + pesosSubList$_{2}$)
					\STATE i $\leftarrow$ 3
					\WHILE{(i $<$ long)} 
						\STATE resA $\leftarrow$ resC
						\STATE resC $\leftarrow$ max(resC, resB + pesosSubList$_{i}$)
						\STATE resB $\leftarrow$ resA
						\STATE i $\leftarrow$ i + 1
					\ENDWHILE	
				\STATE devolver resC
			\ENDIF
		\end{algorithmic}
	\end{algorithm}
	
\newpage
	
\subsubsection{Explicaci'on del Pseudoc'odigo}
Vamos a detallar el pseudoc'odigo de la versi'on iterativa, dado que la versi'on recursiva fue detallada anteriormente.\\
La funci'on matchingMaximoIter toma como par'ametro de entrada una lista con los pesos de las aristas siguiendo un orden particular, respetando las adyacencias. 'Esta solamente calcula el m'aximo resultante del valor que se obtiene de las dos llamadas a la funci'on matchingMaximoAuxIter, los cuales corresponden a la posibilidad de elegir o no la 'ultima arista. Ambos llamados ya no tienen como par'ametro de entrada un grafo c'iclico, sino un camino simple.\\
En matchingMaximoIterAux existen tres casos bases:
\begin{itemize}
	\item 0 aristas, devuelve como resultado 0.
	\item 1 arista, devuelve como resultado el peso de dicha arisa.
	\item 2 aristas, devuelve como resultado el m'aximo entre sus pesos.
	\item 3 aristas, devuelve como resultado el m'aximo entre el peso correspondiente a la segunda arista y la suma de los pesos correspondientes a la primera y la tercera, ya que estas 'ultimas no tienen v'ertices en com'un.\\
\\
Luego se incializan tres variables que acumular'an los resultados parciales(las llamaremos {\bf resA}, {\bf resB}, {\bf resC}), con los primeros tres valores de la lista de pesos de manera similar a los casos base.\\
Dentro del ciclo lo que se realiza es un intercambio entre los valores de modo tal que la variable {\bf resC} almacene el valor resultante de calcular el m'aximo entre su valor y la suma de {\bf resB} con la i-esima posici'on de la lista de pesos, con i el n'umero de iteraci'on actual.\\ 
Por 'ultimo devuelve el valor almacenado en {\bf resC}.
	
\end{itemize}

\subsection{Complejidad}

Vamos a analizar las dos funciones utilizadas por separado, para luego concluir la complejidad final:\\
\begin{itemize}
	\item Complejidad de la funci'on matchingMaximo:\\
	Esta funci'on recibe un arreglo que contiene los pesos de las aristas y su longitud que llamaremos $pesos$ y $long$ respectivamente, y  devuelve el m'aximo entre dos llamados a matchingMaximoAux, uno con el arreglo original sin el 'ultimo peso y el otro con el arreglo original sin el primero ni los dos ultimos pesos. En este 'ultimo llamado el algoritmo estar'ia eligiendo el 'ultimo peso, entonces lo suma a este llamado. La funci'on matchingMaximoAux devuelve un entero. Realizar una suma tiene un costo constante, y el m'aximo entre dos enteros tambien, dado que es una comparaci'on.\\
	\item Complejidad de la funci'on matchingMaximoAux:\\
	Esta funci'on recibe como par'ametros una sublista del arreglo de pesos original y su longitud que llamamos $pesosSubList$ y $subLong$ respectivamente.\\
	En principio el algoritmo genera cuatro enteros y realiza cuatro comparaciones lo cual tiene un costo constante. Luego otras cuatro asignaciones y calcula el m'aximo entre dos enteros, nuevamente costo constante. Lo siguiente a ejecutar es un ciclo desde $i=3$ hasta $subLong$. Dentro del ciclo hay cuatro asignaciones con costo constante y nuevamente el c'alculo de un m'aximo entre dos enteros tambi'en con costo constante. Por lo tanto el costo del ciclo se determina 'unicamente por la cantidad de veces que se ejecuta, ya que las operaciones realizadas dentro de este son despreciables, $subLong - 3$ veces.\\ 
	Entonces la complejidad de matchingMaximoAux es O($subLong - 3$).\\ 
	\item Conclusi'on:
	Ahora bien, matchingMaximo hace dos llamados a matchingMaximoAux uno con $subLong = long - 1$ y el otro con $subLong = long - 3$. Entonces considerando ambos casos, la complejidad final de la funci'on queda de la siguiente forma:\\
	O($(long - 1) + (long - 3)$) = O($2 * (long - 4)$) $\in$ \fbox{O($long$)}.\\
	\newline 
	Por lo tanto la complejidad de matchingMaximo es lineal con respecto al tama'no del arreglo de entrada.\\    
\end{itemize}


\subsection{Gr\'aficos}
 
En esta secci'on la idea es estudiar el comportamiento del algoritmo en la pr'actica. Queremos ver si el algoritmo se comporta de igual manera que lo calculado anteriormente de forma te'orica. Para ello lo que hacemos es contar la cantidad de operaciones que realiza el algoritmo para las distintas instancias de prueba. A continuci'on presentaremos 3 casos para intentar determinar el comportamiento en la pr'actica del algoritmo.\\
Adem'as vamos a graficar el comportamiento de la funci'on recursiva comparandolo con nuestro algoritmo. \\
\\
Sea $n$ la cantidad de aristas del Grafo, los casos son los siguientes:

	\begin{enumerate}
	
	\item Casos con $n$ $\in$ [3, 1000] con pesos aleatorios en las aristas.\\ 
	En esta instancia queremos ver si efectivamente la complejidad del algoritmo en la pr'actica es lineal como calculamos anteriormente en la complejidad te'orica. Para ello generamos un arreglo con $n$ $\in$ [3, 1000]. A cada posici'on del arreglo le asignamos un valor al azar representando el peso de una arista del grafo.\\
\\	
	El gr'afico que obtuvimos es el siguiente:
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{./graficos/ej1/CantOp1000.jpg}
		\caption{Cantidad de Operaciones $n$ $\in$ [3, 1000]}
	\end{figure}
	
	Como vemos en el gr'afico, efectivamente el algoritmo tiene complejidad lineal en la pr'actica con respecto a la cantidad de operaciones. As'i confirmamos lo que suponiamos mediante la prueba de esta instancia.\\

\newpage
	
	\item Casos con $n$ $\in$ [3, 3000] comparando con un grafo de aristas con pesos todos iguales.\\ 
	En est'a instancia la idea es poder observar la cantidad de operaciones que realiza el algoritmo para casos en los que los pesos de las aristas son todos iguales. Los queremos comparar con los casos aleatorios anteriores para observar el comportamiento en este caso.\\
	Suponemos que la cantidad de operaciones no deber'ia variar con respecto a los casos con pesos al azar ya que no influye el peso de una arista en la cantidad de operaciones que realiza el algoritmo.\\
	La intenci'on es mostrar que esto se cumple con el siguiente gr'afico:\\ 
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{./graficos/ej1/CantOp3000=.jpg}
		\caption{Cantidad de Operaciones $n$ $\in$ [3, 3000] comparanco con aristas de pesos iguales}
	\end{figure}
	
	En este caso podemos concluir como hab'iamos supuesto anteriormente que con los pesos todos iguales, la cantidad de operaciones con respecto al tama\~no del arreglo es la misma que para casos con pesos al azar. Las rectas est'an superpuestas por lo que el gr'afico queda confuso. Por ende concluimos que no importa cuales sean los pesos en las aristas sino que la cantidad de operaciones depende 'unicamente de la cantidad de aristas del grafo.\\ 

\newpage
	
	\item Casos con $n$ $\in$ [3, 30] comparando el algoritmo con la funci'on recursiva.\\ 
	La idea de esta instancia es tratar de ver cuanto mejora el comportamiento del algoritmo con el uso de la t'ecnica de programaci'on din'amica, comparando con la funci'on recursiva encontrada anteriormente que tambien resuelve el problema. Lo que esperamos ver es que nuestro algoritmo implementado mediante la programaci'on din'amica sea mucho m'as eficiente en cuanto a la cantidad de operaciones que la funci'on recursiva.\\  
	En este caso mediremos la cantidad de operaciones en escala logar'itmica para notar bien la diferencia entre ambos.\\
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{./graficos/ej1/iterativaVsRecursiva.jpg}
		\caption{Cantidad de Operaciones $n$ $\in$ [3, 30] comparando con la funci'on recursiva}
	\end{figure}
	Como podemos observar en este gr'afico, la funci'on recursiva es de orden exponencial con respecto a la cantidad de arisatas del grafo(en el gr'afico es lineal pero esta medido en orden logar'itmico). Vemos que crece mucho m'as r'apido que el algoritmo din'amico a medida que aumenta el tama'no de entrada.
	\end{enumerate} 
\subsection{Conclusi\'on}
La concluci'on que podemos sacar de este ejercicio es la ventaja del uso de la t'ecnica de programaci'on din'amica respecto de otras t'ecnicas que construyen la soluci'on a partir de subproblemas de menor tama'no, dado que en nuestro contexto estos subproblemas no son completamente independientes entre s'i por lo que no contemplar esta situaci'on podr'ia producir una severa reducci'on de la eficiencia. Al resolver este problema, notamos la importante diferencia de eficiencia que produce la funci'on iterativa que utiliza programaci'on din'amica en contraste con la funci'on recursiva que resuelve el problema. Como se vi'o en uno de los casos de prueba, pasamos de una complejidad exponencial a una lineal gracias a esta t'ecnica. Esto se debe a que usar simplemente recursi'on produce repeticiones de c'alculos, lo que con la t'ecnica de programaci'on din'amica estas repeticiones no se producen, logrando as'i una mejora sustancial de la complejidad. Consiguiendose el objetivo del orden de la complejidad propuesto para este ejercicio.